/*************************************************************************
 * File Name:    Jump_Game_II.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/16 15:06:55
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Jump Game II
 |
 | Given an array of non-negative integers, you are initially positioned
 | at the first index of the array.
 |
 | Each element in the array represents your maximum jump length at that position.
 |
 | Your goal is to reach the last index in the minimum number of jumps.
 |
 | For example:
 | Given array A = [2,3,1,1,4]
 |
 | The minimum number of jumps to reach the last index is 2. (Jump 1 step
 | from index 0 to 1, then 3 steps to the last index.)
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    int jump(int A[], int n)
    {
        int i, t, base, step, ans;
        
        ans = base = 0;
        step = A[0];
        while (base < n - 1) {
            ++ans;
            t = 0;
            for (i = 1; i <= step && base + step < n; ++i) {
                t = max(t, A[base + i] - step + i);
            }
            base += step;
            step = t;
        }
        return ans;
    }
};

